package com.github.bobjoy.java.algorithmic;

import org.junit.Assert;
import org.junit.Test;

/**
 * 时间复杂度：
 *      时间复杂度来说，递归与非递归的方式都一样，在最坏的情况下的时间复杂度为O(log2 N)，即x次之后找到，n/2^x=1;最好情况下为O（1），即第一次就找到。
 *
 * 空间复杂度：
 *      算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数
 *      非递归方式（search1）：由于辅助空间是常数级别的，所以空间复杂度是O(1);
 *      递归方式（search2）： 递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的，空间复杂度：O(log2N )
 */
public class BinarySearchDemo {

    private int search1(int[] nums, int target) {
        int start = 0;
        int high = nums.length - 1;


        while (start <= high) {
            int middle = (start + high)/2;
            if (target < nums[middle]) {
                high = middle - 1;
            } else if (target > nums[middle]) {
                start = middle + 1;
            } else {
                return middle;
            }
        }

        return -1;
    }

    private int search2(int[] nums, int target, int start, int high) {
        if (start > high || target < nums[start] || target > nums[high]) {
            return -1;
        }

        int middle = (start + high) / 2;
        if (target < nums[middle]) {
            high = middle - 1;
            return search2(nums, target, start, high);
        } else if (target > nums[middle]) {
            start = middle + 1;
            return search2(nums, target, start, high);
        } else {
            return middle;
        }
    }

    @Test
    public void testSearch() {

        int[] nums = {1,4,7,56,86,122,146,216,319,453};

        int index = search1(nums, 216);
        Assert.assertEquals(7, index);

        index = search2(nums, 86, 0, nums.length-1);
        Assert.assertEquals(4, index);
    }

}
